/**
 * https://leetcode.cn/problems/minimize-the-maximum-difference-of-pairs/submissions/564312099/
 * 2616. 最小化数对的最大差值
 * medium 陈贝纯 2024.09.13
 * 二分搜索
 */

class Solution {
public:
    bool check(vector<int>& nums,int p,int mid){
        for(int i=1;i<nums.size();++i){
            if(nums[i]-nums[i-1]<=mid){
                p--;
                i++;
            }
        }
            return p<=0;
    }
    int minimizeMax(vector<int>& nums, int p) {
        int n=nums.size();
        sort(nums.begin(),nums.end());
        int r=nums[n-1];
        int l=0;
        int ans=0;
        while(l<=r){
            int mid=l+(r-l)/2;
            if(check(nums,p,mid)){
                ans=mid;
                r=mid-1;
            }else
            l=mid+1;
        }
        return ans;
    }
};